# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        def dfs(val, string, height):
            if len(string) == 0:
                return None
            root = TreeNode(val)
            leftIndex = -1
            rightIndex = -1
            d = 0
            i = 0
            leftVal = None
            rightVal = None
            while i < len(string):
                s = string[i]
                if s == '-':
                    d += 1
                else:
                    if d == height + 1:
                        number = string[i]
                        while i + 1 < len(string) and string[i + 1] != '-':
                            i += 1
                            number += string[i]
                        if leftIndex == -1:
                            leftIndex = i
                            leftVal = int(number)
                        else:
                            rightIndex = i
                            rightVal = int(number)
                    d = 0
                i += 1

            if leftIndex == -1:
                return root
            if rightIndex == -1:
                root.left = dfs(leftVal, string[leftIndex:], height + 1)
            else:
                root.left = dfs(leftVal, string[leftIndex:rightIndex],
                                height + 1)
                root.right = dfs(rightVal, string[rightIndex:], height + 1)
            return root

        i = 0
        number = ""
        while i < len(S) and S[i] != '-':
            number += S[i]
            i += 1
        return dfs(int(number), S[i - 1:], 0)
